package LeetCode.month01.day14;

import java.util.ArrayList;
import java.util.List;

public class No200bfs {
    public int numIslands(char[][] grid) {
        int nr = grid.length;
        int nc = grid[0].length;
        int num = 0;
        for (int r = 0; r < nr; r++) {
            for (int c = 0; c < nc; c++) {
                if(grid[r][c]=='1'){
                    num++;
                    grid[r][c] = '0';
                    List<Integer> list = new ArrayList<>();
                    list.add(r*nc+c);
                    while(!list.isEmpty()){
                        int n = list.remove(0);
                        int row = n/nc;
                        int col = n%nc;
                        if(row-1>=0&&grid[row-1][col]=='1'){
                            grid[row-1][col]='0';
                            list.add((row-1)*nc+col);
                        }
                        if(row+1<nr&&grid[row+1][col]=='1'){
                            grid[row+1][col]='0';
                            list.add(((row+1)*nc+col));
                        }
                        if(col+1<nc&&grid[row][col+1]=='1'){
                            grid[row][col+1]='0';
                            list.add(row*nc+col+1);
                        }
                        if(col-1>=0&&grid[row][col-1]=='1'){
                            grid[row][col-1]='0';
                            list.add(row*nc+col-1);
                        }
                    }
                }
            }
        }
        return num;
    }
}
